#ifndef __OCC_VALUE_CU__
#define __OCC_VALUE_CU__

#include"Settings.h"
#include"cutil_inline.h"
#include"cutil_math.h"
#include "Index.h"
#include "integer.h"
#include "OccValue_cpu.h"

////////////
//only for debug, temp code
static uint64 count = 0;

void resetCount() {
	count = 0;
}

uint64 getCount() {
	return count;
}


inline void incCount() {
//	count += 1;
}


/*host memory corresponding to the constant memory*/
static unsigned int h_CountValue[ALPHABET_SIZE + 1] = {0};
static int h_shiftTable[MAX_QUERY_LENGTH] = {0};


void initShiftTable() {
	for(int pos = 0; pos < QUERY_LENGTH; pos++) {
		h_shiftTable[pos] = BIT_PER_CHAR*(CHAR_PER_WORD - 1  - (pos&(CHAR_PER_WORD - 1)));
	}
}


void initCountValue(BWT* bwt) {
	printf("here begin\n");
	printf("address: %d\n", bwt);
	unsigned int bwtCountValueMemSize = (ALPHABET_SIZE + 1) * sizeof(int);
	memcpy(h_CountValue, bwt->countValue, bwtCountValueMemSize);
	printf("here end\n");
}


char host_getCharFromQueries(unsigned int * Queries, unsigned int queryId, unsigned int pos)
{
	unsigned int shift, rowIndex;
	char c=0;

	rowIndex = pos / CHAR_PER_WORD;
	shift = BIT_PER_CHAR * ( CHAR_PER_WORD -1  - (pos % CHAR_PER_WORD));
	c = (( Queries[queryId * QUERY_SIZE_IN_WORD + rowIndex])>>shift)&3;

	return c;
}

unsigned int host_DNAOccCount_2Layer(unsigned int *dna, unsigned int index,
                        char character, unsigned int backward) {
 	unsigned int wordToCount, charToCount;
        unsigned int i;
        unsigned int sum = 0;
        unsigned long long d, b, a, mask;
	incCount();
	wordToCount = index>>(5);
        charToCount = index - wordToCount * 32;

        dna -= backward * 8;
        
	unsigned long long *dd = ((unsigned long long *)dna);
        i = backward ? 3 : 0;
        while(wordToCount > 0) {
                d = dd[i];
                b = (d >> 1);
                b ^= ((character & 0x2) ? 0 : 0xFFFFFFFFFFFFFFFF);
                a = d ^ ((character & 0x1) ? 0 : 0xFFFFFFFFFFFFFFFF);
                a &= b;
                a &= 0x5555555555555555;
                sum += host_popcll(a);
                i = (backward ? i-1 : i+1);
                wordToCount--;
        }
	assert(i >= 0);
        if (charToCount > 0) {
                d = dd[i];
                b = (d >> 1);
                b ^= ((character & 0x2) ? 0 : 0xFFFFFFFFFFFFFFFF);
                a = d ^ ((character & 0x1) ? 0 : 0xFFFFFFFFFFFFFFFF);
                a &= b;
                if (charToCount < 16) {
                        mask = (0x00000000FFFFFFFF << (32-charToCount*2)) & 0x00000000FFFFFFFF;
                } else {
                        mask = (0xFFFFFFFF00000000 << (64-charToCount*2)) | 0x00000000FFFFFFFF;
                }
                if (backward)
                        mask = host_brevll(mask);
                a &= (mask & 0x5555555555555555);
                sum += host_popcll(a);
        }
	return sum;	
}
 
unsigned int host_GPUDNAOccCount(unsigned int *dna, unsigned int index, 
			char character, unsigned int backward) {
			
			
	unsigned int wordToCount, charToCount;
	unsigned int i;
	unsigned int sum = 0;
	unsigned long long d, b, a, mask;

	incCount();
	
	
	//wordToCount = index / 32;
	wordToCount = index>>(5);
	charToCount = index - wordToCount * 32;
	dna -= backward * 4;
	ulonglong2 dd;
	
	//ulonglong2 is a 16Byte = 128bit CUDA vector
	//.x is the first 8Byte while .y is the last.
	dd = *((ulonglong2*)dna);
	i = 0;
	if (wordToCount > 0) { // i = 0
		d = backward ? dd.y : dd.x;
		b = (d >> 1);
		b ^= ((character & 0x2) ? 0 : 0xFFFFFFFFFFFFFFFF);
		a = d ^ ((character & 0x1) ? 0 : 0xFFFFFFFFFFFFFFFF);
		a &= b;
		a &= 0x5555555555555555;
		sum += host_popcll(a);
		i = 1;
	}
	
	if (wordToCount == 2 || charToCount > 0) {
		if (backward) i = 3 - i;
		if (wordToCount == 2) charToCount = 32;
		d = (i & 1) ? dd.y : dd.x;
		b = (d >> 1);
		b ^= ((character & 0x2) ? 0 : 0xFFFFFFFFFFFFFFFF);
		a = d ^ ((character & 0x1) ? 0 : 0xFFFFFFFFFFFFFFFF);
		a &= b;
		if (charToCount < 16) {
			mask = (0x00000000FFFFFFFF << (32-charToCount*2)) & 0x00000000FFFFFFFF;
			//mask = (0x00000000FFFFFFFF << (32-(charToCount<<1))) & 0x00000000FFFFFFFF;
		} else {
			mask = (0xFFFFFFFF00000000 << (64-charToCount*2)) | 0x00000000FFFFFFFF;
			//mask = (0xFFFFFFFF00000000 << (64-(charToCount<<1))) | 0x00000000FFFFFFFF;
		}
		if (backward)
			mask = host_brevll(mask);
		a &= (mask & 0x5555555555555555);
		sum += host_popcll(a);
	}

	return sum;
}

void host_DNAAllOccCount_2Layer(unsigned int *dna, unsigned int index,
                                        unsigned int backward, unsigned int occCount[]) {
        unsigned int wordToCount, charToCount;
        unsigned int i;
        unsigned long long d, b, a, mask;

        incCount();

        //wordToCount = index / 32;
        wordToCount = index >> 5;
        charToCount = index - wordToCount * 32;
        dna -= backward * 8;
        unsigned long long  *dd = ((unsigned long long*)dna);
        i = backward ? 3 : 0;
        while(wordToCount > 0) {
                d = dd[i];
                for(int j=0; j < ALPHABET_SIZE; j++) {
                        b = (d >> 1);
                        b ^= ((j & 0x2) ? 0 : 0xFFFFFFFFFFFFFFFF);
                        a = d ^ ((j & 0x1) ? 0 : 0xFFFFFFFFFFFFFFFF);
                        a &= b;
                        a &= 0x5555555555555555;
                        if (backward)
                                occCount[j] -= host_popcll(a);
                        else
                                occCount[j] += host_popcll(a);
		}
                i = backward ? i-1 :i+1;
                wordToCount--;
        }
	assert(i >= 0);
        if (charToCount > 0) {
                d = dd[i];
                for(int j=0; j<ALPHABET_SIZE; j++) {
                        b = (d >> 1);
                        b ^= ((j & 0x2) ? 0 : 0xFFFFFFFFFFFFFFFF);
                        a = d ^ ((j & 0x1) ? 0 : 0xFFFFFFFFFFFFFFFF);
                        a &= b;
                        if (charToCount < 16) {
                                mask = (0x00000000FFFFFFFF << (32-charToCount*2)) & 0x00000000FFFFFFFF;
                        } else {
                                mask = (0xFFFFFFFF00000000 << (64-charToCount*2)) | 0x00000000FFFFFFFF;
                        }
                        if (backward)
                                mask = host_brevll(mask);
                        a &= (mask & 0x5555555555555555);
                        if (backward)
                                occCount[j] -= host_popcll(a);
                        else
                                occCount[j] += host_popcll(a);
		}
        }
}
 
void host_GPUDNAAllOccCount(unsigned int *dna, unsigned int index, 
					unsigned int backward, unsigned int occCount[]) {
	unsigned int wordToCount, charToCount;
	unsigned int i;
	unsigned long long d, b, a, mask;
	
	incCount();
	
	//wordToCount = index / 32;
	wordToCount = index >> 5;
	charToCount = index - wordToCount * 32;
	dna -= backward * 4;
	ulonglong2 dd;
	dd = *((ulonglong2*)dna);
	i = 0;
	if (wordToCount > 0) { // i = 0
		d = backward ? dd.y : dd.x;
#pragma unroll 4
		for (int j = 0; j < ALPHABET_SIZE; ++j) {
			b = (d >> 1);
			b ^= ((j & 0x2) ? 0 : 0xFFFFFFFFFFFFFFFF);
			a = d ^ ((j & 0x1) ? 0 : 0xFFFFFFFFFFFFFFFF);
			a &= b;
			a &= 0x5555555555555555;
			if (backward)
				occCount[j] -= host_popcll(a);
			else
				occCount[j] += host_popcll(a);
		}
		i = 1;
	}
	
	if (wordToCount == 2 || charToCount > 0) {
		if (backward) i = 3 - i;
		if (wordToCount == 2) charToCount = 32;
		d = (i & 1) ? dd.y : dd.x;
#pragma unroll 4
		for (int j = 0; j < ALPHABET_SIZE; ++j) {
			b = (d >> 1);
			b ^= ((j & 0x2) ? 0 : 0xFFFFFFFFFFFFFFFF);
			a = d ^ ((j & 0x1) ? 0 : 0xFFFFFFFFFFFFFFFF);
			a &= b;
			if (charToCount < 16) {
				mask = (0x00000000FFFFFFFF << (32-charToCount*2)) & 0x00000000FFFFFFFF;
			} else {
				mask = (0xFFFFFFFF00000000 << (64-charToCount*2)) | 0x00000000FFFFFFFF;
			}
			if (backward)
				mask = host_brevll(mask);
			a &= (mask & 0x5555555555555555);
			if (backward)
				occCount[j] -= host_popcll(a);
			else
				occCount[j] += host_popcll(a);
		}
	}

}
unsigned int host_OccMinorValue(unsigned int *occMinor, unsigned int MinorIndex, char c) {
        unsigned int MinorExplicitIndex = MinorIndex / 2;
        if(MinorIndex % 2) {
                return (occMinor[MinorExplicitIndex * ALPHABET_SIZE + c] & 0xFFFF);
        }
        else {
                return (occMinor[MinorExplicitIndex * ALPHABET_SIZE + c] >> 16);
        }
}

unsigned int host_BWTOccValue_2Layer(unsigned int *bwt, unsigned int *occMajor, unsigned int *occMinor,
					unsigned int index, char c, unsigned int inverseSa0) {
	index -= (index > inverseSa0);
	unsigned int occMajorIndex = (index + (OCC_MINOR_INTERVAL / 2) - 1)/OCC_MAJOR_INTERVAL;
	unsigned int occMinorIndex = ( index + (OCC_MINOR_INTERVAL / 2) - 1) / OCC_MINOR_INTERVAL;
	unsigned int occIndex = occMinorIndex * OCC_MINOR_INTERVAL;
	unsigned int occValue = occMajor[occMajorIndex * ALPHABET_SIZE + c] + host_OccMinorValue(occMinor, occMinorIndex, c);

	if(occIndex != index) {
		unsigned int cnt = host_DNAOccCount_2Layer(bwt + (occIndex>>LOG2_CHAR_PER_WORD),
                                                        host_usad(index, occIndex, 0), c, occIndex > index); 
		return occIndex > index ? occValue - cnt : occValue + cnt;
	} else {
		return occValue;
	}
}

// copied from BWT.c 
unsigned int host_GPUBWTOccValue(unsigned int *bwt, unsigned int *occ, 
			unsigned int index, char c, unsigned int inverseSa0) {

			
	index -= (index > inverseSa0);
	//unsigned int occExplicitIndex = (index + GPU_OCC_INTERVAL_DIV_2 - 1) / GPU_OCC_INTERVAL;
	unsigned int occExplicitIndex = (index + GPU_OCC_INTERVAL_DIV_2 - 1)>>LOG2_GPU_OCC_INTERVAL;
	unsigned int occIndex = occExplicitIndex * GPU_OCC_INTERVAL;
	/*using global memory*/
	unsigned int occValue = occ[occExplicitIndex * ALPHABET_SIZE + c];
	/*using texture memory*/
	//int elementId = occExplicitIndex * ALPHABET_SIZE + c;
	//unsigned int occValue = tex2D(texOcc, elementId&65535, elementId>>16);
	if (occIndex != index) {
		//unsigned int cnt = GPUDNAOccCount(bwt + occIndex / CHAR_PER_WORD, 
		//					__usad(index, occIndex, 0), c, occIndex > index);
		unsigned int cnt = host_GPUDNAOccCount(bwt + (occIndex>>LOG2_CHAR_PER_WORD), 
							host_usad(index, occIndex, 0), c, occIndex > index);
		return occIndex > index ? occValue - cnt : occValue + cnt;
	} else {
		return occValue;
	}
}

void host_AllOccMinorValue(unsigned int * occMinor, unsigned int MinorIndex, unsigned int * value) {
	unsigned int MinorExplicitIndex = MinorIndex / 2;
	if(MinorIndex % 2) {
		for(int j=0; j< ALPHABET_SIZE; j++) {
			value[j] = (occMinor[MinorExplicitIndex * ALPHABET_SIZE + j] & 0xFFFF);
		}
	}
	else {
		for(int j=0; j< ALPHABET_SIZE; j++) {
			value[j] = (occMinor[MinorExplicitIndex * ALPHABET_SIZE + j] >> 16);
		}
	}	
}
void host_BWTAllOccValue_2Layer(unsigned int *bwt, unsigned int *occMajor, unsigned int *occMinor,
                                unsigned int index, unsigned int inverseSa0, unsigned int occCount[]) {
	index -= (index > inverseSa0);
	unsigned int occMajorIndex = (index + (OCC_MINOR_INTERVAL / 2) - 1)/OCC_MAJOR_INTERVAL;
	unsigned int occMinorIndex = ( index + (OCC_MINOR_INTERVAL / 2) - 1) / OCC_MINOR_INTERVAL;
	unsigned int occIndex = occMinorIndex * OCC_MINOR_INTERVAL;
	int i;
//	printf("occMajor: %u, occMinor: %u, occIndex: %u\n", occMajorIndex, occMinorIndex, occIndex);	
	host_AllOccMinorValue(occMinor, occMinorIndex, occCount);
	for(i=0; i<ALPHABET_SIZE; i++) {
		occCount[i] += occMajor[occMajorIndex * ALPHABET_SIZE + i];
	}
	
	if(occIndex != index) {
		host_DNAAllOccCount_2Layer(bwt + (occIndex >> LOG2_CHAR_PER_WORD), 
					host_usad(index, occIndex, 0), occIndex > index, occCount);
	}
} 
void host_GPUBWTAllOccValue(unsigned int *bwt, unsigned int *occ, 
				unsigned int index, unsigned int inverseSa0, unsigned int occCount[]) {
	index -= (index > inverseSa0);
	//unsigned int occExplicitIndex = (index + GPU_OCC_INTERVAL_DIV_2 - 1) / GPU_OCC_INTERVAL;
	unsigned int occExplicitIndex = (index + GPU_OCC_INTERVAL_DIV_2 - 1)>>LOG2_GPU_OCC_INTERVAL;
	unsigned int occIndex = occExplicitIndex * GPU_OCC_INTERVAL;
	*((uint4*)occCount) = *((uint4*)(occ + occExplicitIndex * ALPHABET_SIZE));
	
	if (occIndex != index) {
		//GPUDNAAllOccCount(bwt + occIndex / CHAR_PER_WORD, 
		//				__usad(index, occIndex, 0), occIndex > index, occCount);
		host_GPUDNAAllOccCount(bwt + (occIndex>>LOG2_CHAR_PER_WORD), 
						host_usad(index, occIndex, 0), occIndex > index, occCount);
	}	
}


bool host_bwtCalc(BWT *bwt, char baseId, unsigned int * start, unsigned int * end)
{
	if ((*start) > bwt->textLength || (*end) > bwt->textLength || (*end) < (*start))
		return false;

//	unsigned int occ = h_CountValue[baseId];
	unsigned int occ = 0;

#if   LAYER_INDEX_1	
	*start = occ +  host_GPUBWTOccValue(bwt->bwtCode,bwt->GPUOccValue, (*start), baseId,bwt->inverseSa0) + 1;
	*end = occ + host_GPUBWTOccValue(bwt->bwtCode,bwt->GPUOccValue,((*end)+1), baseId,bwt->inverseSa0);
#endif 

#if LAYER_INDEX_2
	*start = occ + host_BWTOccValue_2Layer(bwt->bwtCode, bwt->occMajorValue, bwt->occValue, (*start), baseId,
						bwt->inverseSa0) + 1;
	*end = occ + host_BWTOccValue_2Layer(bwt->bwtCode,bwt->occMajorValue,bwt->occValue, ((*end)+1),
						baseId, bwt->inverseSa0);
#endif
	if (*start <= *end)
		return true;
	return false;
}


bool host_bwtCalcWithOccValue(unsigned int *countValue,char baseId, unsigned int startOccValue,
					unsigned int endOccValue, unsigned int * start, unsigned int * end) {
//	(*start) = h_CountValue[baseId] + startOccValue + 1;
//	(*end) = h_CountValue[baseId] + endOccValue;
	(*start) = startOccValue + 1;
	(*end) = endOccValue;

	if ((*start) <= (*end))
		return true;
	return false;
}


#endif /*__OCC_VALUE_CU__*/
